#include <stdio.h>
#include <stdlib.h>

using namespace std;

class dll_xor {

//static struct node *nodeAlloc();
//	static struct node *xor(struct node *a, struct node *b);
//	static void insertFirst(int value);
//	static void insertLast(int value);
//void dumpList(struct node *, struct node *);

	public:
		dll_xor();
		~dll_xor();


	struct node {
		int value;
		struct node *np;
	};

	struct node *head;
	struct node *tail;

	static struct node *nodeAlloc() {
		return (struct node *) malloc(sizeof(struct node));
	};

	static struct node * xor(struct node *prev, struct node *next) {
		return (struct node*) ((unsigned long) prev ^ (unsigned long) next);
	};

	static void insertFirst(int value) {
		struct node *x;
		x = nodeAlloc();
		x->value = value;

		if (head == NULL && tail == NULL) {
			x->np = NULL;
			head = x;
			tail = x;
		} else {
			x->np = xor(NULL, head);
			head->np = xor(x, head->np);

			head = x;
		}
	}

	static void insertLast(int value) {
		struct node *x;
		x = nodeAlloc();
		x->value = value;

		if (head == NULL && tail == NULL) {
			x->np = NULL;
			head = x;
			tail = x;
		} else {
			x->np = xor(tail, NULL);
			tail->np = xor(tail->np, x);

			tail = x;
		}
	}

//void dumpList(struct node *node, struct node *prev) {
//	if (node != NULL) {
//		printf("\n%d", node->value);
//	dumpList(xor(node->np, prev), node);
//}
//}
}

//------------------

//int main() {
//	insertFirst(7);
//	insertFirst(5);
//	insertFirst(4);
//	insertFirst(2);
//	insertLast(8);
//	insertLast(9);
//	insertLast(10);
//
//	printf("\n------------------\nForward List:");
//
//	dumpList(head, NULL);
//
//	printf("\n------------------\nBackward List:");
//
//	dumpList(tail, NULL);
//
//	return 0;
//}
